package com.wenx.huawei;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] array = Stream.of(5, 4, 8, 7, 3, 19, 2, 6)
                .mapToInt(Integer::byteValue)
                .toArray();

        quickSort(array);

        Arrays.stream(array).forEach(i -> {
            System.out.print(i + " ");
        });

    }

    private static void quickSort(int[] array) {

        if(array == null || array.length == 0 || array.length ==1) {
            return;
        }

        sorts(array,0,array.length-1);

    }

    private static void sorts(int[] array,int left, int right) {

        if(left > right) {
            return;
        }

        int base = array[left];

        int i = left, j = right;

        while (i != j) {

            //先从右边找比基数小的
            while (array[j] >= base && i < j) {
                j--;
            }

            //再从左边找比基数大的数
            while (array[i] <= base && i < j) {
                i++;
            }

            //交换
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        //将基准值放到中央位置
        array[left] = array[i];
        array[i] = base;

        //递归
        //左半部分
        sorts(array,left,i-1);
        //右半部分
        sorts(array,i+1,right);

    }

}
